import sys


def main():
    # 同学总数
    n = int(input())
    mates = list(map(int, input().split()))

    lefts = [0 for _ in range(n)]
    for i in range(0, n):
        for j in range(i):
            if mates[i] > mates[j]:
                lefts[i] = max(lefts[i], lefts[j] + 1)

    rights = [0 for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(n - 1, i, -1):
            if mates[i] > mates[j]:
                rights[i] = max(rights[i], rights[j] + 1)

    res = [lefts[i] + rights[i] for i in range(n)]
    print(n - max(res) - 1)


def main2():
    # 同学总数
    n = int(input())
    mates = list(map(int, input().split()))

    lefts = [0 for _ in range(n)]
    rights = [0 for _ in range(n)]
    res = [0 for _ in range(n)]

    index = 1
    for i in range(1, n):
        if mates[i] > mates[index - 1]:
            res[i] = index
        else:
            l = 0
            r = index - 1
            while l < r:
                mid = (l + r) // 2
                if lefts[mid] > mates[i]:
                    r = mid
                else:
                    l = mid + 1

            lefts[l] = mates[i]
            res[i] = l

    index = 1
    for i in range(n - 2, -1, -1):
        if mates[i] > rights[index - 1]:
            res[i] += index
            rights[index] = mates[i]
            index += 1
        else:
            l = 0
            r = index - 1
            while l < r:
                mid = (l + r) // 2
                if rights[mid] > mates[i]:
                    r = mid
                else:
                    l = mid + 1

    print(n - max(res) - 1)


if __name__ == '__main__':
    with open('../input.txt', "r") as fr:
        sys.stdin = fr
        while True:
            try:
                main2()
            except EOFError:
                break